/*
 * GA.cpp
 *
 *  Created on: 04/07/2011
 *      Author: daniel
 */

#include "GA.h"
#include "GRASP.h"
#include "Operator.h"
#include "LS.h"
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <stdio.h>
#include <list>

bool greater(Solution *a, Solution *b) {
	return (a->cost < b->cost);
}

vector<Solution*> generatePopulation(Solution *problem, int tam,
		double greedyPercentage) {

	vector<Solution*> population;
	vector<int> remaining;
	double percentage = 0;

	if (greedyPercentage >= 0 && greedyPercentage <= 1)
		percentage = greedyPercentage;
	else
		percentage = greedyPercentage / 100;

	for (int i = 0; i < tam; ++i) {

		Solution *s;

		// Porcentaje de individuos aleatorios.
		if (i < tam * percentage) {
			s = new Solution(problem->cityNumber);
			for (int i = 1; i <= problem->cityNumber; ++i) {
				remaining.push_back(i);
			}

			while (!remaining.empty()) {
				int index = rand() % remaining.size();
				s->addCity(remaining[index]);
				remaining.erase(remaining.begin() + index);
			}

			s->C = problem->C;
			s->iniCost = 0;
			s->cost = s->recomputeCost();

			// Los que quedan que sean greedys.
		} else {
			s = GRASP::Greedy(problem, 0);
		}
		population.push_back(s);
	}
	return population;
}

/**
 * Selecciona a los padres usando ruleta.
 */
vector<Solution*> roulette(vector<Solution*> population) {

	vector<Solution*> parents;

	// Calcula la suma de los fitness de todos
	// los individuos.
	double fitSum = 0;
	for (int i = 0; i < population.size(); ++i) {
		fitSum += population[i]->cost;
	}

	// Hasta que no se tengan los dos padres.
	while (parents.size() < 2) {

		double r = (double) rand() / RAND_MAX;
		double acum = 0.0;

		for (int k = 0; k < population.size(); k++) {

			if (acum <= r && r <= acum + population[k]->cost / fitSum) {
				parents.push_back(population[k]);
				break;
			} else {
				acum += (double) population[k]->cost / fitSum;
			}
		}
	}
	return parents;
}

/**
 * Selecciona a dos padres mediante torneo sobre
 * una poblacion.
 */
vector<Solution*> tournament(vector<Solution*> population, int tSize) {

	vector<Solution*> candidates;
	vector<Solution*> parents;

	// Repite un torneo 2 veces, uno por
	// cada padre.
	for (int j = 0; j < 2; ++j) {

		// Selecciona los candidatos.
		for (int i = 0; i < tSize; ++i) {
			int index = (rand() % population.size());
			candidates.push_back(population[index]);
			population.erase(population.begin() + index);
		}

		Solution *min = candidates[0];

		// Elije el mejor candidato.
		for (int i = 1; i < candidates.size(); ++i) {
			if (min->cost > candidates[i]->cost) {
				min = candidates[i];
			}
		}

		// Agrega al padre.
		parents.push_back(min);
		candidates.clear();
	}

	return parents;
}

/**
 * R	eemplaza estrategicamente a los individuos de una poblacion
 * por otros.
 */
vector<Solution*> replacement(vector<Solution*> population,
		vector<Solution*> children) {

	Solution *worse = population[0];
	Solution *best = population[0];

	// Busca al peor de la poblacion.
	for (int j = 1; j < population.size(); j++) {

		if (worse->cost < population[j]->cost) {
			worse = population[j];
		}
	}

	// Busca al mejor de la poblacion.
	for (int j = 1; j < population.size(); j++) {

		if (best->cost > population[j]->cost) {
			best = population[j];
		}
	}

	double epsilon = 0.25 * (best->cost - worse->cost);

	// Para cada hijo.
	for (int i = 0; i < children.size(); ++i) {

		// Si es mejor al peor lo acepta, de lo contrario, lo acepta
		// con una probabilidad.
		double cost = children[i]->cost;
		if ((cost < worse->cost + epsilon || true || (((double) rand())
				/ RAND_MAX) < 0.35)) {

			int index = rand() % population.size();
			population[index] = children[i];
		}
	}

	return population;
}

/**
 * Aplica algoritmo genetico.
 */
Solution *GA::geneticAlgorithm(Solution *problem, int tam, int generations,
		int tSize, int MaxChildren, double Ppair, double Pmut,
		double greedyPercentage) {

	vector<Solution*> children;
	vector<Solution*> population = generatePopulation(problem, tam,
			greedyPercentage);

	Solution *opt = population[0];
	Solution *aux;

	printf("El costo del mejor individuo es: %f\n", population[0]->cost);

	int i = 0;
	while (i < generations) {

		vector<Solution*> parents = tournament(population, tSize);

		// Mientras no se hayan generado todos los
		// hijos.
		int offspring = 0;
		while (offspring < MaxChildren) {

			// Condicion de cruce.
			if (((double) rand()) / RAND_MAX < Ppair) {

				Solution *child = Operator::OX(parents[0], parents[1]);

				// Condicion de mutacion.
				if (((double) rand()) / RAND_MAX < Pmut) {
					aux = child;
					child = Operator::perturbation(child);
					delete aux;
				}

				children.push_back(child);
			}
			offspring++;
		}

		// Reemplazar.
		if (children.size() > 0) {
			population = replacement(population, children);
			children.clear();
		}

		// Guarda al mejor de esta generacion.
		for (int k = 1; k < population.size(); ++k) {
			if (population[k]->cost < opt->cost)
				opt = population[k];
		}

		i++;
	}
	opt->numIter = i;
	//return LS::LocalSearchBI(opt, 700, 500);
	return opt;
}
